1. Field of the Invention
The present invention relates in general to the decoding of information encoded using a Low Density Parity Check code, or LDPC, and more particularly concerns the loading of the input memory of an LDPC decoder with data to be decoded.
It has applications particularly in devices for receiving signals transmitted by satellite, for example according to the satellite digital video broadcasting standard DVB-S2, which stipulates the use of an LDPC code to protect data transmission.
2. Description of the Related Art
LDPC codes are a class of error correction codes invented in 1960 by Robert Gallager of MIT (“Massachusetts Institute of Technology”), constituting an alternative to the Viterbi codes as well as to the more recent turbo codes. LDPC codes are block codes which allow approaching the Shannon Limit. The first commercial standard stipulating the use of an LDPC code is the DVB-S2 standard, which is the second-generation ETSI (“European Telecommunication Standardization Institute”) standard for satellite digital video broadcasting. LDPC coding is included in it for channel coding, to protect the sent data from noise affecting the transmission channel.
With reference to FIG. 1, a generic transmission subsystem contains, on the side of the transmitter 10, a data source 11 (denoted DAT_SRC in the figure), followed by a source encoder 12 (denoted SCR_ENC in the figure), a channel encoder 13 (denoted CH_ENC in the figure), and a modulator 14 (denoted MOD in the figure). The source encoder 12 compresses the data (for example using a standard such as MPEG, H264, etc.) so as to reduce the bit rate of the data to be transmitted. The channel encoder adds redundancy (for example by using an LDPC code) to enable the receiver 30 to correct potential errors due to the noise No introduced into the transmission channel 20. The modulator 14 adapts the signal to the transmission channel (for example, satellite transmission channel, radio transmission channel, etc.). On the receiver side 30, a demodulator 34 (denoted DEMOD in the figure), followed by a channel decoder 33 (denoted CH_DEC in the figure), and a source decoder 32 (denoted SRC_DEC in the figure), perform operations dual to those performed by the modulator 14, the encoder 13, and the encoder 12, respectively. The demodulated and decoded data are then restored to the entity that uses the data 31 (denoted DAT_U in the figure).
LDPC codes are block codes. On the side of the transmitter, the LDPC encoder processes blocks of K information bits, and outputs code words of N bits, also called LDPC frames, where N>K. In other words, it adds N−K redundancy bits which enable the correction of transmission errors on the receiver side. These N−K bits are called parity bits. The code rate is defined as the ratio r=K/N. The smaller the r, the higher the redundancy, and therefore the higher the protection against noise in the transmission channel.
The N−K bits added to each block of K information bits are calculated using an H matrix, called the parity check matrix. This H matrix has N−K rows and N columns. It contains “0” and “1” values, with the latter in low proportions, which is why codes based on such a parity matrix are called low density parity check codes.
With reference to FIG. 2, an N-bit LDPC frame, in which the K low order bits correspond to the information bits and the N−K high order bits correspond to the parity bits, is the code word C delivered by an LDPC encoder which satisfies the relation:H×Ct=0  (1)
The check node degree for a row in the H matrix is the number of “1”values in the row, and the bit node degree for a column in the H matrix is the number of “1” values in the column. There exist two types of LDPC code: the regular codes and the irregular codes. The H matrix for a regular code has a constant number of “1” values per row and per column, meaning that the check node degrees and bit node degrees are constant. Conversely, the H matrix for an irregular code does not have constant check node degrees and/or constant bit node degrees, and is therefore more random in character. The best performance is obtained with irregular codes, but the decoding may then be more difficult. The DVB-S2 standard recommends the use of an H matrix which has constant check node degrees, between 4 and 30 (abbreviated as matrix check node degree), and bit node degrees which may assume three values between 2 and 13.
On the receiver side, the LDPC decoder corrects the erroneous bits by using the relations between the bits in the LDPC frames received through the transmission channel, corresponding to a block of bits C′. These relations are given by the parity check H matrix, which is of course known to the decoder.
To this effect, the errors in the received block of bits C′ are corrected by applying an iterative algorithm so that the corrected block of bits C′ satisfies the relation:C′×Ht=0  (2)
More particularly, the LDPC decoder processes likelihood ratios, for example log-likelihood ratios (LLRs). On the receiver side, there is an LLR for each of the N bits of an LDPC frame which was sent from the transmitter. For a transmitted bit d which has a corresponding signal x received by the LDPC decoder after noise is added to the transmission channel, the LLR ratio for the bit d in relation to the signal x is defined as:
      LLR    ⁡          (      x      )        =            LLR      ⁡              (                  d          /          x                )              =          ln      ⁢                          ⁢                        P          ⁡                      (                          d              =                              0                /                x                                      )                                    P          ⁡                      (                          d              =                              1                /                x                                      )                              where P(d=0/x) is the probability that the transmitted bit d is equal to 0 as a function of the value x received, and P(d=1/x) is the probability that the transmitted bit d is equal to 1 as a function of the value x received. Each LLR is coded in m bits. For example, an LLR assumes negative or positive values whose absolute value increases with the probability that the received bit with which it is associated is equal, for example, to 0 or 1 respectively.
The LLR information bits and the LLR parity bits are distinguished as corresponding respectively to the information bits and the parity bits in the LDPC frame.
The LDPC decoder uses internal metrics, equal in number to the number of “1” values in the H matrix. These metrics are each coded in t bits. The decoder updates them using an iterative algorithm.
With reference to FIG. 3, each iteration comprises update steps performed by row, consisting of determining for each row the first new values for the internal metrics of the row as a function of the other internal metrics of the row (“check node update”), then update steps performed by column, consisting of determining for each column the second new values for the internal metrics of the column as a function of the other internal metrics of the column and the LLR corresponding to this column (“bit-node update”). To decode a received LDPC frame, the decoder performs several iterations in order to restore a block of N data sent. The decoded bits, called hard decision bits, are then obtained by adding the internal metrics by column with the LLRs for the C′ block received, and taking the sign of the result.
In equipment meeting the DVB-S2 standard, the H matrix consists of a first submatrix A which can have parallel blocks of bit nodes, and a second submatrix B which is a bidiagonal matrix. This form of the H matrix implies a certain manner of loading the data into the input memory of the LDPC decoder.
This write constraint is explained below with reference to the diagram in FIG. 4. This figure represents the memory map for a memory unit of the LDPC decoder input memory, where the data are loaded which are received as input to the decoder and must be stored for decoding. Remember that these data correspond to the N LLRs respectively associated with the N bits of an LDPC frame received by the equipment. In principle, an LLR is received with each cycle of the decoder clock signal.
With P as the parallelism index for the LDPC decoder, meaning the number of processors which perform decoding operations in parallel, the memory map has a number m×P of columns and a number
  N  Pof rows. During read operations in page mode the columns may be read simultaneously, obtaining a set of P LLRs coded in m bits each. The
  N  Prows can be broken into two groups: an integer Wa of rows, for example in the upper part of the memory map (above the dashed line), for storing the bits corresponding to the information LLRs; and an integer Wb of rows, for example in the lower part of the memory map (below the dashed line), for storing the bits corresponding to the parity LLRs. The numbers Wa and Wb satisfy the respective relations
  Wa  =                    K        P            ⁢                          ⁢      and      ⁢                          ⁢      Wb        =                            N          -          K                P            .      In the example represented, the parallelism index P is equal to 6.
The first P words of m bits received as input to the decoder, each corresponding to an information LLR, are written side by side to the first row in the memory map (for example, the one located at the top in the upper part 410A of the memory map), for example from right to left. The next P words of m bits, which also each correspond to an information LLR, are written side by side to the second row, still from right to left. The process continues in this way, as shown by the horizontal arrows in the figure, until the last P words of m bits corresponding to an information LLR received for the frame concerned have been written to the Wath row in the memory map.
The Wb words of m bits which are then received as input to the decoder, and which each correspond to a parity LLR, are successively written one below another to the Wb rows in the lower part of the memory map, for example from the top to bottom, in a group of m columns located for example in the rightmost part of the lower part of the memory map. The next Wb words of m bits, which also each correspond to a parity LLR, are then written, still from top to bottom, to the Wb rows in the lower part 410b of the memory map in another group of m columns, located immediately to the left of the previous group. The process continues in this way, as shown by the vertical arrows in the figure, until the last Wb words of m bits corresponding to the last parity LLRs received for the frame concerned have been written to the Wb rows in the lower part of the memory map, in the pth group of m columns furthest to the left in the memory map.